package com.chengzhi.structure;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.SynchronousQueue;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;

/**
 * @description:
 * @author: ruanchengzhi
 * @create: 2020-03-14 15:24
 **/
public class TrieTest {
    public static void main(String[] args) {
//        char[][] board = {{'o', 'a', 'a', 'n'}, {'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'}};
//        String[] words = {"oath", "pea", "eat", "rain"};
//        System.out.println(findWords(board, words));

        ExecutorService cachedThreadPool = new ThreadPoolExecutor(4, Runtime.getRuntime().availableProcessors() * 2,
                0, TimeUnit.MILLISECONDS, new SynchronousQueue<>(), r -> new Thread(r, "ThreadTest"));
        cachedThreadPool.execute(() -> System.out.println("111"));
        cachedThreadPool.execute(() -> {
            try {
                Thread.sleep(1000L);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("222");
        });
        cachedThreadPool.execute(() -> System.out.println("333"));
        cachedThreadPool.execute(() -> System.out.println("444"));

    }

    /**
     * 给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。
     * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
     * <p>
     * words = ["oath","pea","eat","rain"] and board =
     * [
     * ['o','a','a','n'],
     * ['e','t','a','e'],
     * ['i','h','k','r'],
     * ['i','f','l','v']
     * ]
     * <p>
     * 输出: ["eat","oath"]
     *
     * @param board
     * @param words
     * @return: java.util.List<java.lang.String>
     * @author: ruanchengzhi
     * @date: 2020/5/8
     */
    public static List<String> findWords(char[][] board, String[] words) {
        Set<String> resultList = new HashSet<>();
        if (words.length == 0 || board.length == 0) {
            return new ArrayList<>(resultList);
        }
        Trie trie = new Trie();
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < words.length; i++) {
            trie.add(words[i]);
        }
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, visited, "", i, j, resultList, trie);
            }
        }
        return new ArrayList<>(resultList);
    }

    private static void dfs(char[][] board, boolean[][] visited, String str, int i, int j, Set<String> resultList, Trie trie) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return;
        }
        if (visited[i][j]) {
            return;
        }
        str += board[i][j];
        if (!trie.containsPreFix(str)) {
            return;
        }
        if (trie.contains(str)) {
            resultList.add(str);
        }
        visited[i][j] = true;
        dfs(board, visited, str, i - 1, j, resultList, trie);
        dfs(board, visited, str, i + 1, j, resultList, trie);
        dfs(board, visited, str, i, j - 1, resultList, trie);
        dfs(board, visited, str, i, j + 1, resultList, trie);
        visited[i][j] = false;
    }

}
